package main.Q401_500;

//import org.junit.Test;

import java.util.*;

public class Q451_460 {
    public static void main(String[] args) {
        System.out.println("Question451：根据字符出现频率排序");
        System.out.println("Question452：用最少数量的箭引爆气球");
        int[][] points = new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        System.out.println(new Question452().findMinArrowShots(points));
        System.out.println("Question453：");
        System.out.println("Question454：四数相加Ⅱ");
        System.out.println("Question455：分发饼干");
        System.out.println("Question456：");
        System.out.println("Question457：");
        System.out.println("Question458：");
        System.out.println("Question459：重复的子字符串");
        System.out.println("Question460：");
    }
}

class Question451 {
    public String frequencySort(String s) {
        StringBuffer result = new StringBuffer();
        char[] str = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : str) map.put(c, map.getOrDefault(c, 0) + 1);//记录频率
        PriorityQueue<int[]> bigHeap = new PriorityQueue<>(new Comparator<int[]>() {//频率入堆并排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] != o2[1] ? o2[1] - o1[1] : o1[0] - o2[0];//先比较频率，字母序无所谓
            }
        });
        for (char c : map.keySet()) bigHeap.add(new int[]{c, map.get(c)});//入堆
        while (!bigHeap.isEmpty()) {
            int[] cur = bigHeap.poll();
            int c = cur[0], k = cur[1];
            while (k-- > 0) result.append((char) c);
        }
        return result.toString();
    }
}

class Question452 {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
        int result=1;
        int lastEnd=points[0][1];
        for(int i=1;i<points.length;i++){
            if(points[i][0] > lastEnd){//当前区间左端点大于 前区间右端点即没有重叠,箭的数量需要+1
                result++;
                lastEnd=points[i][1];
            }
        }
        return result;
    }
}

class Question454 {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {//预处理进行嵌套降维
        int count = 0;
        Map<Integer, Integer> map12 = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {//预处理1、2数组
            for (int j = 0; j < nums2.length; j++)
                map12.put(nums1[i] + nums2[j], map12.getOrDefault(nums1[i] + nums2[j], 0) + 1);
        }
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                if (map12.containsKey(-1 * (nums3[i] + nums4[j]))) {
                    count += map12.get(-1 * (nums3[i] + nums4[j]));
                }
            }
        }
        return count;
    }
}

class Question455 {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0, i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (g[i] <= s[j]) {//当胃口小于等于饼干大小时，投喂
                count++;
                i++;
                j++;
            } else j++;//当胃口大于饼干大小时，换大饼干
        }
        return count;
    }
}

class Question459 {
    public boolean repeatedSubstringPattern(String s) {
        char[] str = s.toCharArray();
        if (s.length() < 2) return false;
        int i = 0, j = 1, subLength = 0;
        boolean flag = true;
        String substring = "";
        while (j < s.length()) {
            flag = true;//重置
            if (str[i] == str[j]) {
                substring = s.substring(0, j);//截取子串
                subLength = j - i;//子串长度
                String temp = "";
                if (s.length() % subLength == 0) {//整数倍截取
                    for (int k = 0; k < s.length() / subLength; k++) {
                        temp = s.substring(k * subLength, (k + 1) * subLength);
                        if (!substring.equals(temp)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) return true;
                }
            }
            j++;
        }
        return false;
    }
}